import java.util.Scanner;
 class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;

     TreeNode() {
     }

     TreeNode(int val) {
         this.val = val;
     }

     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }

     /* 1 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。*/
     public class Solution {
         public boolean isSameTree(TreeNode p, TreeNode q) {
             if ((p == null && q != null) || (p != null && q == null))
                 return false;
             if (p == null && q == null)
                 return true;
             if (p.val != q.val)
                 return false;
             return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
         }


 /* 2 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。*/

         public boolean isSubtree(TreeNode root, TreeNode subRoot) {
             if (root == null)
                 return false;
             if (isSameTree(root, subRoot))
                 return true;
             if (isSubtree(root.left, subRoot))
                 return true;
             if (isSubtree(root.right, subRoot))
                 return true;
             return false;
         }

         /*  3 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。*/
         public TreeNode invertTree(TreeNode root) {
             if (root == null)
                 return null;
             TreeNode tmp = root.left;
             root.left = root.right;
             root.right = tmp;
             invertTree(root.left);
             invertTree(root.right);
             return root;
         }

         public int getHeight(TreeNode root) {
             if (root == null)
                 return 0;
             int leftHeight = getHeight(root.left);
             int rightHeight = getHeight(root.right);
             return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
         }

         //4 给定一个二叉树，判断它是否是
         //平衡二叉树
         //平衡二叉树
         //平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。
         public boolean isBalanced(TreeNode root) {
             if (root == null)
                 return true;
             int leftHeight = getHeight(root.left);
             int rightHeight = getHeight(root.right);
             return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left)
                     && isBalanced(root.right);
         }

         //5 给你一个二叉树的根节点 root ， 检查它是否轴对称。
         public boolean isSymmetric(TreeNode root) {
             if (root == null)
                 return true;
             return isSymmetricChild(root.left, root.right);
         }

         public boolean isSymmetricChild(TreeNode p, TreeNode q) {
             if ((p == null && q != null) || (p != null && q == null))
                 return false;
             if (p == null && q == null)
                 return true;
             if (p.val != q.val)
                 return false;
             return isSymmetricChild(p.left, q.right) && isSymmetricChild(p.right, q.left);
         }

         //6 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
         // 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
         // 建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
         public static void main(String[] args) {
             Scanner in = new Scanner(System.in);
             while (in.hasNextLine()) {
                 String str = in.nextLine();
                 TreeNode root = createTree(str);
                 inorder(root);

             }

         }

         public  int i;

         public  TreeNode createTree(String str) {
             TreeNode root = null;
             if (str.charAt(i) != '#') {
                 root = new TreeNode(str.charAt(i));
                 i++;
                 root.left = createTree(str);
                 root.right = createTree(str);
             } else {
                 i++;
             }
             return root;
         }

         public  void inorder(TreeNode root) {
             if (root == null)
                 return;
             inorder(root.left);
             System.out.print(root.val + " ");
             inorder(root.right);

         }
     }
 }

